package cn.edu.nju.ws.sview.reasoning;

import java.sql.SQLException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

import cn.edu.nju.ws.sview.rdf.BlankNode;
import cn.edu.nju.ws.sview.rdf.Resource;
import cn.edu.nju.ws.sview.rdf.URIResource;

/**
 * @author Gong Saisai
 * production memory store rules
 * 
 */
public class ProductionMemory {
	private HashMap<Predicate, HashSet<Rule>> rules;
	// 谓词依赖图，存储每个谓词通过若干规则依赖于其它谓词
	private HashMap<Predicate, HashMap<Predicate, HashSet<Rule>>> PDG;

	public ProductionMemory() {
		rules = new HashMap<Predicate, HashSet<Rule>>();
		PDG = new HashMap<Predicate, HashMap<Predicate, HashSet<Rule>>>();
	}

	public ProductionMemory(Collection<Rule> o) {
		PDG = new HashMap<Predicate, HashMap<Predicate, HashSet<Rule>>>();
		Iterator<Rule> itor = o.iterator();
		while (itor.hasNext()) {
			Rule rule = itor.next();
			this.addRule(rule);
		}
	}

	/**
	 * 返回规则库所有规则
	 * @return
	 */
	public HashSet<Rule> getAllRules() {
		HashSet<Rule> res = new HashSet<Rule>();
		Iterator<Predicate> itor = rules.keySet().iterator();
		while (itor.hasNext()) {
			res.addAll(rules.get(itor.next()));
		}
		return res;
	}

	/**
	 * 返回头部谓词是pred的那些规则集合
	 * @param pred
	 * @return
	 */
	public HashSet<Rule> getRulesWithPred(Predicate pred) {
		HashSet<Rule> res = new HashSet<Rule>();
		if (rules.containsKey(pred))
			res.addAll(rules.get(pred));
		return res;
	}

	/**
	 * 增加一个规则，同时更新谓词依赖图
	 * @param rule
	 */
	public void addRule(Rule rule) {
		Predicate pred = rule.getHead().getPredicate();
		if (!rules.containsKey(pred)) {
			HashSet<Rule> set = new HashSet<Rule>();
			set.add(rule);
			rules.put(pred, set);
		} else {
			HashSet<Rule> set = rules.get(pred);
			set.add(rule);
		}
		updatePDG(rule);
	}

	/**
	 * 更新索引
	 * 
	 * @param rule
	 */
	private void updatePDG(Rule rule) {
		Predicate headPred = rule.getHead().getPredicate();
		ArrayList<Atom<Term>> list = rule.getBody();
		HashMap<Predicate, HashSet<Rule>> dependency = null;
		if (!PDG.containsKey(headPred)) {
			dependency = new HashMap<Predicate, HashSet<Rule>>();
			PDG.put(headPred, dependency);
		} else
			dependency = PDG.get(headPred);
		for (int i = 0; i < list.size(); i++) {
			Predicate pred = list.get(i).getPredicate();
			HashSet<Rule> set = new HashSet<Rule>();
			if (!dependency.containsKey(pred)) {
				dependency.put(pred, set);
			} else {
				set = dependency.get(pred);
			}
			set.add(rule);
		}
	}

	
	/**
	 * 返回定义查询q相关的自定义规则列表（排除模式推理需要的规则），并按照依赖关系排序。
	 *  期间，需要与数据管理进行若干次交互，递归地得到相关的规则
	 * 本方法供外部使用，不新建一个规则库，=
	 * @param q. 相应的查询
	 * @return
	 * @throws SQLException 
	 */
	public static ArrayList<Rule> getRules(Predicate pred){
		ArrayList<Rule> rules = new ArrayList<Rule>();
		ArrayList<Predicate> TODOList = new ArrayList<Predicate>();
		HashSet<Predicate> visited = new HashSet<Predicate>();
		visited.add(pred) ;
		TODOList.add(pred) ;
		while(TODOList.size()>0){
			Predicate p = TODOList.remove(0) ;
			HashSet<Rule> ruleSet  = Repository.getInstance().getRulesByHead(p);
			for(Rule r:ruleSet){
				if(p.equals(pred)){
					r.setFlag(true);
				}
				rules.add(r) ;
//				ArrayList<Atom<Term>> body = r.getBody() ;
//				for(Atom<Term> atom:body){
//					Predicate relPred = atom.getPredicate();
//					Resource resource = relPred.getResource();
//						
//					if(resource instanceof URIResource){
//						resource = (URIResource)resource;
//						if(((URIResource) resource).isInternalURI()&&!(visited.contains(relPred))){
//							visited.add(relPred) ;
//							TODOList.add(relPred) ;
//						}
//					}
//					
//				}
			}
		}
		return rules;
	}

	/**
	 * 返回与回答查询q相关的规则列表，并按照依赖关系排序。
	 *  期间，需要与数据管理进行若干次交互，递归地得到相关的规则
	 * 
	 * @param q. 相应的查询
	 * @return
	 * @throws SQLException 
	 */
	public ArrayList<Rule> getRelevantRules(Atom<Term> q) throws SQLException {
		ArrayList<Predicate> TODOList = new ArrayList<Predicate>();
		HashSet<Predicate> visited = new HashSet<Predicate>();
		Predicate pred = q.getPredicate();
		visited.add(pred) ;
		TODOList.add(pred) ;
		while(TODOList.size()>0){
			Predicate p = TODOList.remove(0) ;
			HashSet<Rule> ruleSet  = Repository.getInstance().getRulesByHead(p);
			//Maybe additional rules have been added
			if(this.rules.containsKey(p)){
			ruleSet.addAll(this.rules.get(p));
			}
			for(Rule r:ruleSet){
				this.addRule(r) ;
				ArrayList<Atom<Term>> body = r.getBody() ;
				for(Atom<Term> atom:body){
					Predicate relPred = atom.getPredicate();
					if(!(visited.contains(relPred))){
						visited.add(relPred) ;
						TODOList.add(relPred) ;
					}
				}
			}
		}
		
//		HashSet<Rule> sameAsRules = makeSameAsRules(visited);
//		for(Rule r:sameAsRules)
//			this.addRule(r) ;
		
		ArrayList<Rule> rules = new ArrayList<Rule>(this.getAllRules());
		return rules;
	}
	
//	public HashSet<Rule> makeSameAsRules(HashSet<Predicate> visited) throws SQLException{
//		HashSet<Rule> set = new HashSet<Rule>();
//		//The sameAs URI need to be checked
//		Resource mySameAs = EquivalentToFactory.getInstance().getEquivalentToURI() ;
//		Predicate mySameAsPredicate = new Predicate(mySameAs,2);
//		Term x = new Variable("x");
//		Term y = new Variable("y") ;
//		Term z = new Variable("z") ;
//		/*sameAs(x,y):-sameAs(y,x)*/
//		ArrayList<Term> symBody = new ArrayList<Term>();
//		ArrayList<Term> symHead = new ArrayList<Term>();
//		symBody.add(y);
//		symBody.add(x) ;
//		symHead.add(x) ;
//		symHead.add(y) ;
//		Atom<Term> headAtom = new Atom<Term>(mySameAsPredicate,symHead);
//		Atom<Term> bodyAtom = new Atom<Term>(mySameAsPredicate,symBody);
//		ArrayList<Atom<Term>> bodyLiterals = new ArrayList<Atom<Term>>();
//		bodyLiterals.add(bodyAtom) ;
//		//provenance of the rule is temporary?
//		Rule symrule = new Rule(headAtom,bodyLiterals,ProvenanceFactory.getInstance().createProvFromTemporary());
//		set.add(symrule) ;
//		for (Predicate predicate : visited) {
//			if (predicate.getArity() == 2) {
//				/* p(z,y):-p(x,y),sameAs(x,z) */
//				ArrayList<Term> firstTerms = new ArrayList<Term>();
//				ArrayList<Term> secondTerms = new ArrayList<Term>();
//				ArrayList<Term> thirdTerms = new ArrayList<Term>();
//				firstTerms.add(z);
//				firstTerms.add(y);
//				secondTerms.add(x);
//				secondTerms.add(y);
//				thirdTerms.add(x);
//				thirdTerms.add(z);
//				Atom<Term> firstAtom = new Atom<Term>(predicate, firstTerms);
//				Atom<Term> secondAtom = new Atom<Term>(predicate, secondTerms);
//				Atom<Term> thirdAtom = new Atom<Term>(mySameAsPredicate,
//						thirdTerms);
//				ArrayList<Atom<Term>> bodyByS = new ArrayList<Atom<Term>>();
//				bodyByS.add(secondAtom);
//				bodyByS.add(thirdAtom);
//				Rule ruleByS = new Rule(firstAtom, bodyByS, ProvenanceFactory
//						.getInstance().createProvFromTemporary());
//				set.add(ruleByS);
//				/* p(x,z):-p(x,y),sameAs(y,z) */
//				firstTerms = new ArrayList<Term>();
//				secondTerms = new ArrayList<Term>();
//				thirdTerms = new ArrayList<Term>();
//				firstTerms.add(x);
//				firstTerms.add(z);
//				secondTerms.add(x);
//				secondTerms.add(y);
//				thirdTerms.add(y);
//				thirdTerms.add(z);
//				firstAtom = new Atom<Term>(predicate, firstTerms);
//				secondAtom = new Atom<Term>(predicate, secondTerms);
//				thirdAtom = new Atom<Term>(mySameAsPredicate, thirdTerms);
//				ArrayList<Atom<Term>> bodyByO = new ArrayList<Atom<Term>>();
//				bodyByO.add(secondAtom);
//				bodyByO.add(thirdAtom);
//				Rule ruleByO = new Rule(firstAtom, bodyByO, ProvenanceFactory
//						.getInstance().createProvFromTemporary());
//				set.add(ruleByO);
//			}else{//arity = 1
//				/*c(y):-c(x),sameAs(x,y)*/
//				ArrayList<Term> firstTerms = new ArrayList<Term>();
//				ArrayList<Term> secondTerms = new ArrayList<Term>();
//				ArrayList<Term> thirdTerms = new ArrayList<Term>();
//				firstTerms.add(y) ;
//				secondTerms.add(x) ;
//				thirdTerms.add(x) ;
//				thirdTerms.add(y) ;
//				Atom<Term> firstAtom = new Atom<Term>(predicate, firstTerms);
//				Atom<Term> secondAtom = new Atom<Term>(predicate, secondTerms);
//				Atom<Term> thirdAtom = new Atom<Term>(mySameAsPredicate,thirdTerms);
//				ArrayList<Atom<Term>> body = new ArrayList<Atom<Term>>();
//				body.add(secondAtom) ;
//				body.add(thirdAtom) ;
//				Rule rule = new Rule(firstAtom, body, ProvenanceFactory
//						.getInstance().createProvFromTemporary());
//				set.add(rule) ;
//			}
//		}
//		return set;
//	}
	
	/**
	 * 根据谓词依赖图对与回答查询q相关的规则进行排序并返回排序结果
	 * @param q.相应的查询
	 * @return.排序结果
	 */
	public ArrayList<Rule> sort(Atom<Term> q){
		Predicate pred  = q.getPredicate();
		ArrayList<Rule> ruleList = new ArrayList<Rule>();
		ArrayList<Predicate> predList = getPredTopology(pred);
		for (int i = 0; i < predList.size(); i++) {
			Predicate _predicate = predList.get(i);
			if (this.rules.containsKey(_predicate)) {
				HashSet<Rule> set = this.rules.get(_predicate);
				ruleList.addAll(set);
			}
		}
		return ruleList;
	}

	/**
	 * 按照谓词依赖图来得到谓词拓扑序。方法：两遍深度优先遍历
	 * @param pred
	 * @return
	 */
	private ArrayList<Predicate> getPredTopology(Predicate pred) {
		ArrayList<Predicate> reverseOrder = new ArrayList<Predicate>();
		HashMap<Predicate, ArrayList<Predicate>> reverseGraph = new HashMap<Predicate, ArrayList<Predicate>>();
		ArrayList<Predicate> finish = new ArrayList<Predicate>();
		HashSet<Predicate> visited = new HashSet<Predicate>();
		firstDFS(finish, pred, reverseGraph, visited);
		visited.clear();
		for (int i = finish.size() - 1; i >= 0; i--) {
			Predicate _predicate = finish.get(i);
			if (!visited.contains(_predicate))
				secondDFS(_predicate, reverseGraph, reverseOrder, visited);
		}
		Collections.reverse(reverseOrder);
		return reverseOrder;
	}

	private void firstDFS(ArrayList<Predicate> finish, Predicate pred,
			HashMap<Predicate, ArrayList<Predicate>> reverseGraph,
			HashSet<Predicate> visited) {
		visited.add(pred);
		if (this.PDG.get(pred) == null) {
			finish.add(pred);
			return;
		}
		Iterator<Predicate> itor = this.PDG.get(pred).keySet().iterator();
		while (itor.hasNext()) {
			Predicate _predicate = itor.next();
			addEdge(reverseGraph, _predicate, pred);
			if (!visited.contains(_predicate))
				firstDFS(finish, _predicate, reverseGraph, visited);
		}
		finish.add(pred);
	}

	private void secondDFS(Predicate pred,
			final HashMap<Predicate, ArrayList<Predicate>> reverseGraph,
			ArrayList<Predicate> reverseOrder, HashSet<Predicate> visited) {
		visited.add(pred);
		if (reverseGraph.get(pred) == null) {
			reverseOrder.add(pred);
			return;
		}
		Iterator<Predicate> itor = reverseGraph.get(pred).iterator();
		while (itor.hasNext()) {
			Predicate _predicate = itor.next();
			if (!visited.contains(_predicate))
				secondDFS(_predicate, reverseGraph, reverseOrder, visited);
		}
		reverseOrder.add(pred);
	}

	private void addEdge(HashMap<Predicate, ArrayList<Predicate>> reverseGraph,
			Predicate source, Predicate obj) {
		if (!reverseGraph.containsKey(source)) {
			ArrayList<Predicate> list = new ArrayList<Predicate>();
			list.add(obj);
			reverseGraph.put(source, list);
		} else {
			ArrayList<Predicate> list = reverseGraph.get(source);
			list.add(obj);
		}
		return;
	}
    
	public void reset(){
		this.rules.clear();
		this.PDG.clear();
		this.rules = null;
		this.PDG=null;
	}
	
	public String toString() {
		StringBuffer sb = new StringBuffer();
		HashSet<Rule> allRules = getAllRules();
		Iterator<Rule> itor = allRules.iterator();
		while (itor.hasNext()) {
			sb.append(itor.next() + "\n");
		}
		return sb.toString();
	}
}
